#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class RandomListNode:
    def __init__(self, x, next=None):
        self.label = x
        self.next = next
        self.random = None


class Solution:
    # @param head: A RandomListNode
    # @return: A RandomListNode
    def copyRandomList(self, head):
        if not head:
            return head

        self.head = head

        self.double(head)
        self.copy_random()
        return self.disconnect()

    def double(self, head):
        # old new, old new...
        node = head

        while node:
            node_copy = RandomListNode(node.label)
            node_next = node.next

            node.next = node_copy
            node_copy.next = node_next
            node = node_next

    def copy_random(self):
        node = self.head

        while node:
            copy_next = node.next
            real_next = node.next.next      # copy_next.next

            if node.random:
                copy_next.random = node.random.next

            node = real_next

    def disconnect(self):
        dummy_old_head = old_tail = RandomListNode('dummy')
        dummy_new_head = new_tail = RandomListNode('dummy')

        node = self.head

        while node:
            copy_next = node.next
            real_next = node.next.next      # copy_next.next

            # disconnect
            old_tail.next = node
            new_tail.next = copy_next

            old_tail = node
            new_tail = copy_next

            # drive loop
            node = real_next

        old_tail.next = None
        new_tail.next = None

        # print(dummy_old_head.next.label)
        # print(dummy_new_head.next.label)
        # print(dummy_new_head.next.next.label)
        return dummy_new_head.next


def main():
    print("start main")

    v5 = RandomListNode(10)
    v4 = RandomListNode(8, v5)
    v3 = RandomListNode(6, v4)
    v2 = RandomListNode(4, v3)
    v1 = RandomListNode(2, v2)
    vm = RandomListNode(1, v1)


    s = Solution()
    ret = s.copyRandomList(vm)
    print(ret.label)


if __name__ == "__main__":
    main()
